`
https://leetcode.cn/problems/interleaving-string/
`

/**
 * @param {string} s1
 * @param {string} s2
 * @param {string} s3
 * @return {boolean}
 */
var isInterleave = function (s1, s2, s3) {
  const m = s1.length, n = s2.length, t = s3.length;
  if (m + n !== t) return false;

  // 记忆化数组：memo[i][j] 表示 s1[0..i) 和 s2[0..j) 能否组成 s3[0..i+j)
  const memo = new Array(m + 1).fill().map(() => new Array(n + 1).fill(-1));

  function dp(i, j) {
    // 两个字符串都恰好用完
    if (i === m && j === n) {
      return true;
    }

    // 已经计算过
    if (memo[i][j] !== -1) {
      return memo[i][j];
    }

    // s3 中当前需要匹配的位置
    const p = i + j;
    let res = false;

    // 处理边界情况：当某一个字符串已经用完时
    if (i === m) { // s1 已用完，检查 s2 剩余部分是否与 s3 剩余部分完全匹配
      res = s2.slice(j) === s3.slice(p);
    } else if (j === n) { // s2 已用完，检查 s1 剩余部分是否与 s3 剩余部分完全匹配
      res = s1.slice(i) === s3.slice(p);
    } else {
      // 尝试两种可能的匹配路径
      if (s1[i] === s3[p]) {
        res = dp(i + 1, j);
      }
      if (!res && s2[j] === s3[p]) {
        res = dp(i, j + 1);
      }
    }
    memo[i][j] = res;
    return res;
  }

  return dp(0, 0);
};